package lc20240603;

import java.util.*;
import java.util.stream.Collectors;

/**
  * @description 克隆图
  * @author 不知名帅哥
  * @date 2024/6/5 9:12
  * @version 1.0
*/
public class Graph {
    //节点数目
    int vNum;
    //边的数目
    int edgeNum;

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);

        node1.neighbors.add(node2);
        node1.neighbors.add(node4);
        node2.neighbors.add(node1);
        node2.neighbors.add(node3);
        node3.neighbors.add(node2);
        node3.neighbors.add(node4);
        node4.neighbors.add(node1);
        node4.neighbors.add(node3);

        Graph graph=new Graph();
        Node clone=graph.cloneGraph(node1);

        System.out.println("克隆后的图结构：");
        System.out.println("节点 " + clone.val + " 邻居: " + clone.neighbors.stream().map(n -> n.val).collect(Collectors.toList()));
        for (Node n : clone.neighbors) {
            System.out.println("节点 " + n.val + " 邻居: " + n.neighbors.stream().map(ne -> ne.val).collect(Collectors.toList()));
        }
    }

    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        //存储原节点到克隆节点的映射
        Map<Node, Node> visited = new HashMap<>();
        return cloneNode(node,visited);
    }

    private Node cloneNode(Node node, Map<Node, Node> visited) {
        if (visited.containsKey(node)){
            return visited.get(node);
        }
        Node clone=new Node(node.val,new ArrayList<>());
        visited.put(node,clone);
        for (Node neighbor : node.neighbors) {
            clone.neighbors.add(cloneNode(neighbor,visited));
        }
        return clone;
    }
}




